/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: WHY
 * Date: 2022-08-18
 * Time: 23:33
 */
public class TestDemo {
    //空节点直接返回
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null)
            return pHead;
        //添加一个头部节点
        RandomListNode cur = pHead;
        //遍历原始链表，开始复制
        while (cur != null) {
            //拷贝节点
            RandomListNode clone = new RandomListNode(cur.label);
            //将新节点插入到被拷贝的节点后
            clone.next = cur.next;
            cur.next = clone;
            cur = clone.next;
        }
        cur = pHead;
        RandomListNode clone = pHead.next;
        RandomListNode res = pHead.next;
        //连接新链表的random节点
        while (cur != null) {
            //跟随前一个连接random
            if (cur.random == null)
                clone.random = null;
            else
                //后一个节点才是拷贝的
                clone.random = cur.random.next;
            //cur.next必定不为空
            cur = cur.next.next;
            //检查末尾节点
            if (clone.next != null)
                clone = clone.next.next;
        }
        cur = pHead;
        clone = pHead.next;
        //拆分两个链表
        while (cur != null) {
            //cur.next必定不为空
            cur.next = cur.next.next;
            cur = cur.next;
            //检查末尾节点
            if (clone.next != null)
                clone.next = clone.next.next;
            clone = clone.next;
        }
        return res;
    }
}

